/*************************************************************************
	> File Name: 496.下一个更大元素I.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 二  9/ 7 18:46:38 2021
 ************************************************************************/

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        stack<int> mono_stack;
        unordered_map<int, int> ans_map;

        int n = nums1.size(), m = nums2.size();
        for (int i = 0; i < m; i++) {
            ans_map[nums2[i]] = -1;
            //单调栈保存nums2数组每个数右边第一个大于该数的数
            while (!mono_stack.empty() && nums2[i] > mono_stack.top()) {
                ans_map[mono_stack.top()] = nums2[i];
                mono_stack.pop();
            }
            mono_stack.push(nums2[i]);
        }

        for (int i = 0; i < n; i++) {
            ans.push_back(ans_map[nums1[i]]);
        }

        return ans;
    }
};
